МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національний університет «Львівська політехніка» Кафедра САПР Звіт з виконання Лабораторної роботи №4 на тему: ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ з курсу: «Лінгвістичне забезпечення САПР» 1. МЕТА РОБОТИ Ознайомитись з автоматами і лінійними граматиками, проаналізувати їх розв’язок із скінченими автоматами. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ На перших порах наука про мову – лінгвістика зводилась до вивчення природних мов, їх класифікації виявлення різниці та подібності між ними. З виникненням ЕОМ і мов програмування поняття значно розширилось. Виникла потреба створення формального математичного апарату – формальних граматик як механізму описання мов програмування і проектування. Сформулюємо деякі визначення. Неформально визначити можна як підмножину множин всіх речень із слів або символів деякого основного словника. Алфавіт – це непуста скінчена множина елементів, які називаються символами. Ланцюжком називається будь-яка скінчена послідовність алфавіту
. Довжина ланцюжка
дорівнює кількості символів у ньому:
,
. За способом задання правильних ланцюжків формальні граматики поділяються на породжуючі і розпізнаючі. До породжуючих належать граматики, які встановлюють правила побудови будь-якого правильного ланцюжка і визначають структуру так, що не можна побудувати жодного неправильного ланцюжка. Розпізнаючі граматики дають змогу встановити, чи є правильним довільно вибраний ланцюжок, якщо він правильний, визначити його будову. Для побудови трансляторів використовують обидва ці способи: породжуючу граматику для описання синтаксису мови програмування і розпізнаючий пристрій – скінчений автомат як модель алгоритму розпізнавання речень мови. Породжуючою граматикою називається впорядкована четвірка:
. де
- основний термінальний алфавіт;
- скінчений нетермінальний алфавіт;
- початковий нетермінальний символ – аксіома;
- скінчена множина підстановок (продукцій), ліві і праві частини – це ланцюжки
та
, які містять символи термінального
і нетермінального
алфавітів. Символи термінального
алфавіту є елементарними одиницями мови. Символи нетермінального
алфавіту є метазмінними, які використовують при виведені правильних ланцюжків. Початковий символ
- це метазмінна з якої виводяться всі правильні ланцюжки. Множина
– граматичні правила мови, яку визначають. Щоб відрізнити термінальні символи від нетермінальних, прийнято не термінальні символи поміщати в кутові дужки. ФОРМА БЕКУСА-НАУРА Таке подання граматики є нормальною формою Бекуса (БНФ) і є першою метамовою, яка використовувалась для описання синтаксису алгоритмічної мови «Алгол-60». Основним призначенням форми Безуса – Наура є представлення в стислому і компактному вигляді формальних і однозначних правил написання основних конструкцій мови програмування. У формі Бекуса описуються два класи об’єктів: 1. основні символи мови (термінальні символи); 2. мета лінгвістичні змінні (не термінальні символи). Кожна металінгвістика форма описує правила побудови конструкцій мови і складається з двох частин. Ліворуч мета лінгвістична змінна, яка визначає відповідну конструкцію. Далі металінгвістична зв’язка
, що означає «визначається як». Праворуч – формули, що означають один або декілька варіантів побудови конструкції. Для побудови відповідної конструкції необхідно вибрати відповідний варіант з правої частини формули і підставити його замість відповідної металінгвістичної змінної. Такий процес називається і позначається символам
. КЛАСИФІКАЦІЯ ФОРМАЛЬНИХ ГРАМАТИК Вирішальний вплив на властивості мови, складність породження і розпізнавання ланцюжків мають правила підстановки множини
, тобто граматичні правила мови. Класифікація мов буда запропонована в 1959 році американським лінгвістом Н. Хомським. Він запропонував класифікувати формальні мови за типом правил породжуючих граматик. Клас 0. Правила виводу граматики мають таку форму
, без будь-яких обмежень на ланцюжки
та
. Ці мови є моде...